/*
 * Copyright (c) 2021
 * User:LENOVO
 * File:三角形最小路径和.java
 * Date:2021/02/18 14:21:18
 */

package org.bytedance.动态和贪心;

import com.alibaba.fastjson.JSON;
import com.alibaba.fastjson.JSONArray;
import com.alibaba.fastjson.JSONObject;

import java.time.OffsetDateTime;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 给定一个三角形 triangle ，找出自顶向下的最小路径和。
 * 每一步只能移动到下一行中相邻的结点上。
 * 相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
 * 也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
 * <p>
 * 输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
 * 输出：11
 */
public class 三角形最小路径和 {
    public static void main(String[] args) {
        三角形最小路径和 instance = new 三角形最小路径和();
        List<List<Integer>> obj = new ArrayList<>();
        List<JSONArray> inputs = JSONObject.parseObject("[[2],[3,4],[6,5,7],[4,1,8,3]]", obj.getClass());
        List<List<Integer>> collect = inputs.stream().map(item -> JSONArray.parseArray(item.toJSONString(), Integer.class)).collect(Collectors.toList());
        int i = instance.minimumTotal(collect);
        System.out.println(i);
        i = instance.minimumTotal2(collect);
        System.out.println(i);
        i = instance.minimumTotal3(collect);
        System.out.println(i);
        //instance.print(collect);
        //instance.minimumTotal(null);
    }

    public void print(List<List<Integer>> input) {
        if (input == null || input.isEmpty()) return;
        for (List<?> line : input) {
            System.out.println(JSONObject.toJSONString(line));
        }
        System.out.println();
    }

    public void print(int[][] inputs) {
        if (inputs == null || inputs.length == 0) return;
        for (int i = 0; i < inputs.length; i++) {
            System.out.println(JSONObject.toJSONString(inputs[i]));
        }
    }

    /**
     * 自底向上的方法
     *
     * @param triangle
     * @return
     */
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0) return 0;
        int[] dp = new int[triangle.size() + 1];
        for (int i = triangle.size() - 1; i >= 0; i--) {
            for (int j = 0; j < triangle.get(i).size(); j++) {
                dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
            }
        }
        return dp[0];
    }


    /**
     * 自顶向下的方法
     *
     * @param triangle
     * @return
     */
    public int minimumTotal2(List<List<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0) return 0;
        int[] dp = new int[triangle.size() + 1];
        dp[0] = 0;
        if (triangle.size() > 0) dp[1] = triangle.get(0).get(0);
        int min = 0;
        for (int i = 1; i < triangle.size(); i++) {
            if (triangle.get(i).get(min) > triangle.get(i).get(min + 1)) min += 1;
            dp[i + 1] = dp[i] + triangle.get(i).get(min);
        }
        return dp[dp.length - 1];
    }


    /**
     * 矩阵做法
     */

    public int minimumTotal3(List<List<Integer>> triangles) {
        if (triangles == null || triangles.size() == 0) throw new IllegalArgumentException("bad param");
        int len = triangles.size();
        int[][] dp = new int[len][len];

        //初始化最底层数值
        for (int i = 0; i < len; i++) {
            dp[len - 1][i] = triangles.get(len - 1).get(i);
        }
        //根据dp函数dp[i][j] = Math.min(dp[i][j+1], dp[i+1][j+1]) + nums
        for (int i = len - 2; i >= 0; i--) {
            for (int j = 0; j < triangles.get(i).size(); j++) {
                dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangles.get(i).get(j);
            }
        }
        return dp[0][0];
    }


}
